#ifndef _LAGRANGE_H_
#define _LAGRANGE_H_
// 拉格朗日插值算法
// 由 n+1 对输入（xi, yi）,i = 0,1,2,...,n 构建一个拉格朗日插值函数
#include <iostream>

namespace sy{
namespace interpolation{


#define INVALIDFLOAT (*(reinterpret_cast<float *>(&inValidFloat)))

unsigned long inValidFloat = 0x7f800000;


typedef  
struct
{
    float *x;
    float *y;
    int n;
}lagrange;


// 创建一个拉格朗日插值函数
// param x, y   : x,y 为 (xi, yi), i = 0,1,2,...,n 中的 x, y
// param n      : (xi, yi), i = 0, 1, 2, ..., n 中的 n
// return       : failed return a nullptr

lagrange* CreateLagrange(float *x, float *y, int n)
{
    if(nullptr == x || nullptr == y || n <= 0)
    {
        std::cout << "InValid params" << std::endl;
        return nullptr;
    }

    lagrange *ret = new lagrange;
    if(nullptr == ret)
    {
        std::cout << "Memory apply failed!!!" << std::endl;
        return ret;
    }
    ret->n = n;

    ret->x = new float[n + 1];
    if(nullptr == ret->x)
    {
        std::cout << "Memory apply for array X failed!!!" << std::endl;
        delete ret;
        ret = nullptr;
        return ret;
    }

    ret->y = new float[n + 1];
    if(nullptr == ret->y)
    {
        std::cout << "Memory apply for array Y failed!!!" << std::endl;
        delete [] ret->x;
        delete ret;
        ret = nullptr;
        return ret;
    }

    for(int i = 0; i <= n; ++i)
    {
        ret->x[i] = x[i];
        ret->y[i] = y[i];
    }
    return ret;
}

// 销毁一个拉个朗日插值函数
void DestoryLangrange(lagrange *pLag)
{
    if(pLag != nullptr)
    {
        if(pLag->x != nullptr)
            delete[] pLag->x;
        if(pLag->y != nullptr)
            delete[] pLag->y;
        delete pLag;
    }
}

float Li(unsigned int i, lagrange *pLag, float x)
{
    float ret = 1.0f;
    for(int j = 0; j < pLag->n; ++j)
    {
        if(i == j)
            continue;
        ret *= (x - pLag->x[j]) / (pLag->x[i] - pLag->x[j]);
    }
    return ret;
}

float Ln(lagrange *pLag, float x)
{
    float ret = 0.0f;
    for(int i = 0; i < pLag->n; ++i)
    {
        ret += Li(i,pLag, x) * pLag->y[i];
    }
    return ret;
}

// 从一个拉格朗日函数中获取一个插值
float GetValue(lagrange *pLag, float x)
{
    float ret;
    if(pLag == nullptr) // 拉格朗日函数无效，返回一个无效的 float 值
        return INVALIDFLOAT;
    ret = Ln(pLag, x);

    return ret;
}

std::ostream & operator<<(std::ostream &os,const lagrange& tmp)
{
    std::cout << "插值函数(an*x^n + ... + a2*x^2 + a1*x + a0)的 n ：" << tmp.n << std::endl;
    std::cout << "插值点 :" << std::endl;
    for(int i = 0; i <= tmp.n; ++i)
    {
        std::cout << "    " << i+1 << ": (" << tmp.x[i] << ", " << tmp.y[i] << ")" << std::endl;
    }
    return os;
}


}
}
#endif // _LAGRANGE_H_